Celestin Apprentice 7/Apprentice-Release7.iso/Environments/Small Eiffel 0.4.8/lib_std/dictionary.e

Text File | 1997-04-13 | 10.1 KB | 516 lines | [TEXT/ttxt]

-- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C)
-- Dominique COLNET and Suzanne COLLIN -- [e-mail]
--
class DICTIONARY[V,K]
--
-- Associative memory. Values of type `V' are stored using Keys of type `K'.
--

inherit
   ANY
      redefine is_equal, copy
      end;

creation make, with_capacity

feature {DICTIONARY}

   keys: ARRAY[K];
     -- Index range [1 .. N].
     -- Storage for keys.

   store: ARRAY[V];
     -- Index range [1 .. N].
     -- Storage for items. An item and the corresponding key
     -- are stored at the same index.

   buckets: FIXED_ARRAY[INTEGER];
     -- Index range [0 .. modulus-1].
     -- Entry is a hash code value. Return 0 when hash code not used or
     -- gives the start of the corresponding list in `chain'.

   chain: ARRAY[INTEGER];
     -- Index range [1 .. N].
     -- Chaining of `free' slot and used slot. Value 0 is an end of
     -- list.

   free: INTEGER;
     -- First element of the free list in `chain' or 0 when no more
     -- space.

   modulus: INTEGER;
     -- To compute a hash value in range [0 .. modulus-1].

   Min_size: INTEGER is 16;
     -- Minimum value for N of range [1.. N];

   has_mem: INTEGER;
     -- Memory of the last look in `keys'/`store' or 0 when no
     -- previous successfull looking.

   item_mem, item_mem_i, item_mem_j: INTEGER;
     -- Memory of the last look using `item'.

feature {NONE}

   make is
     -- Internal initial storage size of the dictionary is set to
     -- the default `Min_size' value. Then, tuning of needed
     -- storage size is done automatically according to usage.
     -- If you are really sure that your dictionary is always
     -- really bigger than `Min_size', you may use `with_capacity'
     -- to save some execution time.
      do
     modulus := 2 * Min_size;
     !!buckets.make(modulus);
     !!chain.make(1,Min_size);
     !!store.make(1,Min_size);
     !!keys.make(1,Min_size);
     initialize;
      end;

   with_capacity(medium_size: INTEGER) is
     -- May be used to save some execution time if one is sure
     -- that storage size will rapidly become really bigger than
     -- `Min_size'. When first `remove' occurs, storage size may
     -- naturally become smaller than `medium_size'. Afterall,
     -- tuning of storage size is done automatically according to
     -- usage.
      local
     i: INTEGER;
      do
     from
        i := Min_size;
     until
        i >= medium_size
     loop
        i := 2 * i;
     end;
     modulus := 2 * i;
     !!buckets.make(modulus);
     !!chain.make(1,i);
     !!store.make(1,i);
     !!keys.make(1,i);
     initialize;
      end;

   initialize is
      local
     i: INTEGER;
      do
     count := 0;
     free := 1;
     has_mem := 0;
     item_mem := 0;
     from
        i := 1;
     until
        i = chain.count
     loop
        chain.put (i + 1, i);
        i := i + 1;
     end;
     chain.put(0,i);
     from
        i := 0;
     until
        i >= modulus
     loop
        buckets.put (0,i);
        i := i + 1;
     end;
      end;

feature

   count: INTEGER;
     -- Actual `count' of stored elements.

   empty: BOOLEAN is
      do
     Result := count = 0;
      ensure
     count = 0 implies Result
      end;

   at, infix "@" (k: K): V is
     -- Return the item stored at key `k'.
      require
     has(k)
      local
     foo: BOOLEAN;
      do
     foo := has(k);
     Result := store.item(has_mem);
      end;

   has(k: K): BOOLEAN is
     -- Is there an item currently associated with key 'k' ?
      do
     if has_mem = 0 or else not k.is_equal(keys.item(has_mem)) then
        from
           has_mem := buckets.item(k.hash_code \\ modulus);
        until
           has_mem = 0 or else k.is_equal(keys.item(has_mem))
        loop
           has_mem := chain.item(has_mem);
        end;
     end;
     Result := (has_mem /= 0);
      end;

   key_at(x: V): K is
     -- Retrieve the key used for `x'.
      local
     i: INTEGER;
      do
     from
        i := 1;
     until
        i > count or else (x = item(i))
     loop
        i := i + 1;
     end;
     if i <= count then
        Result := key(i);
     end;
      end;

   put(x: V; k: K) is
     -- If there is as yet no key `k' in the dictionary, enter
     -- it with item `x'. Otherwise overwrite the item associated
     -- with key `k'.
      local
     hash: INTEGER;
      do
     hash := k.hash_code \\ modulus;
     if has_mem = 0 or else not k.is_equal(keys.item(has_mem)) then
        from
           has_mem := buckets.item (hash);
        until
           has_mem = 0 or else k.is_equal (keys.item (has_mem))
        loop
           has_mem := chain.item (has_mem);
        end;
        if has_mem = 0 then
           if count >= store.count then
          expand;
           end;
           keys.put(k, free);
           store.put(x, free);
           has_mem := free;
           free :=chain.item(free);
           chain.put(buckets.item(hash),has_mem);
           buckets.put(has_mem,hash);
           count := count + 1;
           if count > modulus * 2 then
          resize(2 * modulus);
           end;
        end;
     else
        store.put(x,has_mem);
     end;
     item_mem := 0;
      end;

   remove(k: K) is
     -- If there is an entry for key `k' remove it.
     -- Otherwise the call has no effect.
      local
     hash: INTEGER;
     n, p: INTEGER;
      do
     hash := k.hash_code \\ modulus;
     from
        n := buckets.item(hash);
     until
        n = 0 or else k.is_equal (keys.item(n))
     loop
        p := n;
        n := chain.item(n);
     end;
     if n /= 0 then
        if p /= 0 then
           chain.put(chain.item(n),p);
        else
           buckets.put(chain.item(n),hash);
        end;
        chain.put(free,n);
        free := n;
        count := count - 1;
        if n = has_mem then
           has_mem := 0;
        end;
        if count < store.count // 4 and then count > Min_size then
           shrink;
        end;
     end;
     item_mem := 0;
      end;

   is_equal(other: like current): BOOLEAN is
      local
     i: INTEGER;
     k: K;
      do
     if count = other.count then
        from
           i := 1;
           Result := true;
        until
           not Result or else i > count
        loop
           k := key(i);
           if other.has(k) then
          Result := equal_like(item(i),other.at(k));
           else
          Result := false;
           end;
           i := i + 1;
        end;
     end;
      end;

   copy(other: like current) is
      do
     standard_copy(other);
     keys := other.keys.twin;
     store := other.store.twin;
     buckets := other.buckets.twin;
     chain := other.chain.twin;
      end;

feature -- To provide iterating facilities :

   item(i: INTEGER): V is
      require
     1 <= i;
     i <= count;
      do
     if item_mem = 0 then
        first;
        from
        until
           i = item_mem
        loop
           forth;
        end;
        Result := store.item(item_mem_j);
     elseif item_mem <= i then
        from
        until
           i = item_mem
        loop
           forth;
        end;
        Result := store.item(item_mem_j);
     else
        item_mem := 0;
        Result := item(i);
     end;
      ensure
     item_mem = i;
      end;

   key(i: INTEGER): K is
      require
     1 <= i;
     i <= count;
      local
     v: V;
      do
     v := item(i);
     Result := keys.item(item_mem_j);
      end;

feature {NONE}

   first is
      require
     count > 0;
      local
     i: INTEGER;
      do
     from
        i := 0;
     until
        buckets.item(i) /= 0
     loop
        i := i + 1;
     end;
     item_mem_i := i;
     item_mem_j := buckets.item(i);
     item_mem := 1;
      ensure
     item_mem = 1;
      end;

   forth is
      require
     item_mem < count;
      local
     i: INTEGER;
      do
     if chain.item(item_mem_j) /= 0 then
        item_mem_j := chain.item(item_mem_j);
     else
        from
           i := item_mem_i + 1;
        until
           buckets.item(i) /= 0
        loop
           i := i + 1;
        end;
        item_mem_i := i;
        item_mem_j := buckets.item(i);
     end;
     item_mem := item_mem + 1;
      ensure
     item_mem = 1 + old item_mem;
      end;

feature {NONE}

   tmp_buckets: FIXED_ARRAY[INTEGER] is
      once
         !!Result.with_capacity(512);
      end;

   resize(new_mod: INTEGER) is
      local
     hash: INTEGER;
     i, n, p: INTEGER;
      do
         tmp_buckets.copy(buckets);
     buckets.make(new_mod);
     from
        i := 0;
     until
        i >= modulus
     loop
        from
           n := tmp_buckets.item (i);
        until
           n = 0
        loop
           p := chain.item (n);
           hash := keys.item(n).hash_code \\ new_mod ;
           chain.put(buckets.item(hash),n);
           buckets.put(n,hash) ;
           n := p;
        end;
        i := i + 1;
     end;
     modulus := new_mod;
     item_mem := 0;
      end;

   expand is
      local
     i, old_size: INTEGER;
      do
     item_mem := 0;
     old_size := store.count;
     chain.resize (1, 2 * old_size);
     keys.resize  (1, 2 * old_size);
     store.resize (1, 2 * old_size);
     from
        i := old_size + 1;
     until
        i = chain.count
     loop
        chain.put (i + 1, i);
        i := i + 1;
     end;
     chain.put (free, i);
     free := old_size + 1;
      end;

    shrink is
      local
     str  : ARRAY [V];
     kys  : ARRAY [K];
     chn  : ARRAY [INTEGER];
     i, j : INTEGER;
     k    : INTEGER;
      do
     !!kys.make (1, store.count // 2);
     !!str.make (1, store.count // 2);
     !!chn.make (1, store.count // 2);
     from
        i := 1;
        j := 0;
     until
        j >= modulus
     loop
        from
           k := buckets.item (j);
           if k /= 0 then
          buckets.put (i, j);
           end;
        until
           k = 0
        loop
           kys.put (keys.item (k), i);
           str.put (store.item (k), i);
           k := chain.item (k) ;

           if k = 0 then
          chn.put (0, i);
           else
          chn.put (i + 1, i);
           end;
           i := i + 1;
        end;
        j := j + 1;
     end;
     from
        i := count + 1;
     until
        i >= chn.count
     loop
        chn.put (i + 1, i);
        i := i + 1;
     end;
     chn.put (0, i);
     free := count + 1;
     -- *** MLK : chain.free;
     chain := chn;
     -- *** MLK : keys.free;
     keys := kys;
     -- *** MLK : store.free;
     store := str;
     item_mem := 0;
      end;

feature {NONE}

   equal_like(v1, v2: V): BOOLEAN is
     -- Note: to avoid calling `equal' :-(
     -- Because SmallEiffel is not yet able to infer
     -- arguments types.
      do
     if v1.is_expanded_type then
        Result := v1 = v2 or else v1.is_equal(v2);
     elseif v1 = v2 then
        Result := true;
     elseif v1 = Void or else v2 = Void then
     else
        Result := v1.is_equal(v2);
     end;
      end;

invariant

   keys.lower = 1;

   keys.lower = store.lower and store.lower = chain.lower;

   keys.upper = store.upper and store.upper = chain.upper;

   buckets.lower = 0;

   buckets.upper = modulus - 1;

end -- DICTIONARY